import java.util.Arrays;

public class myheap {
    public int[] elem;
    public int usesize;

    public void first_Elem(int[] array) {
        int len = array.length - 1;
        this.elem = new int[len+1];
        for (int i = 0; i <= len; i++) {
            this.elem[i] = array[i];
            usesize++;
        }
    }

    public void creat_heap() {
        for (int parent = (this.usesize - 1 - 1) / 2; parent >= 0; parent--) {
            creat_down(parent, this.usesize);
        }
    }

    public void creat_down(int parent, int usesize) {
        int child = 2 * parent + 1;
        while (child < usesize) {
            //找值最大的孩子结点
            if (child + 1 < usesize && elem[child] < elem[child + 1]) {
                child++;
            }
            //判断根节点
            if (elem[parent] < elem[child]) {
                int tmp = elem[child];
                elem[child] = elem[parent];
                elem[parent] = tmp;
                //判断修改后的根节点
                parent = child;
                child = 2 * child + 1;
            } else {
                break;
            }
        }

    }
    //插入
    public void push(int val){
        //插入到最后面
         if (isFull()){
            elem = Arrays.copyOf(elem,2*elem.length);
        }
        elem[usesize] = val;
        usesize++;

        int child = usesize-1;
        int parent = (child - 1) / 2;
        while (parent >= 0){
            if(elem[parent] < elem[child]){
                int tmp = elem[child];
                elem[child] = elem[parent];
                elem[parent] = tmp;

                child = parent;
                parent = (child-1)/2;
            }else{
                break;
            }

        }


    }
    public void swap(int[] elem,int i,int j){
        int tmp = elem[i];
        elem[i] = elem[j];
        elem[j] = tmp;
    }
    //删除操作

    public void delet(int val){
        if(isEmpty()){
            return ;
        }
        int index = find_index(val);
        swap(this.elem,index,this.usesize-1);
        this.usesize--;
        creat_down(0,this.usesize-1);
        //
    }
    //获取下标
    public  int find_index(int val){
        for (int i = 0; i < usesize; i++) {
            if(val == elem[i]){
                return i;
            }
        }
        return -1;
    }
    //排序
    public  void sort(){
        int end = usesize-1;
        while (end > 0){
            swap(this.elem,0,end);
            creat_down(0,end-1);
            end--;
        }
    }
    public boolean isEmpty(){
        return usesize == 0;
    }
    public boolean isFull(){
        return this.elem.length == usesize;
    }
}


